#include<iostream>
#include<vector>
#include<cstdio>
#define maxsize 255
using namespace std;
vector<int>nt;
vector<int>b;
vector<int>a;
class sstring {
public:
    char data[maxsize+1];
    int length;
    void init() {
        length = 0;
    }
    bool emenpty() {
        if(length==0) return true;
        else return false;
    }
    bool full() {
        if(length==maxsize) return true;
        return false;
    }
    void push_back(char ch) {
        if(full()) {
            cout<<"插入错误，已满";

        }
        length++;
        data[length]=ch;
    }
    void dispaly() {
        if(emenpty()) {
            cout<<"展示错误，为空";

        }
        for(int i=0; i<=length; i++) {
            cout<<data[i];
        }
        cout<<'\n';
    }
    void scan(){
        int n;
        cout<<"请输入插入的字符个数"<<endl;
        cin>>n;
        getchar();
        for(int i=0;i<n;i++){
            char ch=getchar();
            push_back(ch);
            if(full()) break;
        }
    }
    int size() {
        return length;
    }
    void connect(sstring s2) {
        if(full()) {
            cout<<"原字符串已满，请重试";

        }
        if(s2.full()) {
            cout<<"连接的字符串已满，请重试";

        }
        int c=1;
        while(!full()&&c!=s2.length+1){
            data[++length]=s2.data[c++];
        }
    }
   vector<int> BFPP(sstring s2,int mi){
        vector<int> a;
        int start=1;
       int cout;
        for(;start<=length;start++){
            cout=0;
            int i=start;int j=1;
            for(;j<=s2.length;j++,i++){
                if(data[i]!=s2.data[j]){
                    cout++;
                }

            }
            if(cout<=mi){
                a.push_back(start);
            }
        }
        return a;
    }
    void getnext(){
        
        int len=length;
        nt.resize(len+1);
        nt[1]=0;
        int k=1,j=0;
        while(k<=len){
            if(j==0||data[k]==data[j]){
                j++;k++;
                nt[k]=j;
            }
            else {
                j=nt[j];
            }
        }
   
}
   
};  
int kmp(sstring s1,sstring s2){
        s2.getnext();
        int len1=s1.length;
        int len2=s2.size();
        int i=1,j=1;
        while(i<=s1.length&&j<=s2.length){
            if(j==0||s1.data[i]==s2.data[j]){
                j++;i++;
            }
            else {
                j=nt[j];
            }

        }
        
        if(j>=len2) return i-j+1;
        return -1;
    }
    vector<int> BFP(sstring s1,sstring s2){
        vector<int>a;
        int start=1;
        int i=1,j=1,c=0;
        for(;start<=s1.length;start++){
            i=start;j=1;
            while(s1.data[i]==s2.data[j]&&i<=s1.length&&j<=s2.length){
                i++;j++;

            }
            if(j>s2.length){
                a.push_back(start);
            }
        }
        return a;
    }
int main() {
    cout<<"开始创建顺序结构储存字符串"<<endl;
    sstring s1,s2;
    s1.init();
    s2.init();
    cout<<"创建成功"<<endl;
    cout<<"开始插入元素"<<endl;
    s1.scan();
    cout<<"插入成功"<<endl;
    cout<<"开始展示元素";
    s1.dispaly();
    cout<<"开始实现列表相加"<<endl;
    cout<<"开始插入元素"<<endl;
    s2.scan();
    cout<<"插入成功"<<endl;

    cout<<"输出联合的串";
    cout<<"输出串的长度";
    s1.dispaly();
    cout<<"开始实现bf升级版算法";
    a=BFP(s1,s2);
    cout<<"匹配位置为";
    for(int i=0;i<a.size();i++){
        cout<<a[i];
    }
    cout<<endl;
    cout<<"开始执行bf模糊算法";
    a=s1.BFPP(s2,1);
    for(int i=0;i<a.size();i++){
        cout<<a[i];
    }
    cout<<endl;
    cout<<"开始执行kmp算法";
    int c=kmp(s1,s2);
    cout<<c;
    cout<<endl;
    return 0;
}